package leetcode.editor.cn.q1_300.q100;

import java.util.HashSet;
import java.util.Set;

/**
 * 好吧。。看了答案的
 * 自己的想法就是排序用小根堆
 *
 * @author qidi
 * @date 2022-01-12 09:08:17
 */
class Q0128_LongestConsecutiveSequence {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestConsecutive(int[] nums) {
            int len = nums.length;
            if (len < 2) return len;

            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }

            int ans = 0;
            for (int num : set) {
                if (!set.contains(num - 1)) {
                    int cur = 1;
                    while (set.contains(++num)) {
                        cur++;
                    }
                    ans = Math.max(ans, cur);
                }
            }

            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0128_LongestConsecutiveSequence().new Solution();
        System.out.println(solution.longestConsecutive(new int[]{-6, 8, -5, 7, -9, -1, -7, -6, -9, -7, 5, 7, -1, -8, -8, -2, 0}));
        System.out.println(solution.longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
        System.out.println(solution.longestConsecutive(new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}));
    }
}